package com.example.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
 *
 * 输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
 *
 *        5
 *       / \
 *     3    6
 *    / \    \
 *   2   4    8
 *  /        / \
 * 1        7   9
 *
 * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 *
 *  1
 *   \
 *    2
 *     \
 *      3
 *       \
 *        4
 *         \
 *          5
 *           \
 *            6
 *             \
 *              7
 *               \
 *                8
 *                 \
 *                  9
 */
public class Leetcode897_IncreasingBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
        root.right.right = new TreeNode(8);
        root.right.right.left = new TreeNode(7);
        root.right.right.right = new TreeNode(9);

        increasingBST2(root);

    }


    private static TreeNode tmp;

    /**
     * 解法二:中序遍历时修改指针指向
     * @param root
     * @return
     */
    public static TreeNode increasingBST2(TreeNode root) {
        TreeNode head = new TreeNode(-1);
        tmp = head;
        inorder(root);
        return head.right;
    }

    public static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);

        // 在中序遍历的过程中修改节点指向
        tmp.right = root;
        root.left = null;
        tmp = root;

        inorder(root.right);
    }


    /**
     * 解法一:先中序遍历，然后重新构造一棵二叉树返回即可
     *
     * @param root
     * @return
     */
    public static TreeNode increasingBST(TreeNode root) {
        TreeNode res, tmp;
        List<Integer> resList = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        while (root != null || !stack.isEmpty()) {

            while (root != null) {//一直往左走
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            resList.add(root.val);
            root = root.right;

        }

        res = new TreeNode(resList.get(0));
        tmp = res;

        for (int i = 1; i < resList.size(); i++) {
            tmp.right = new TreeNode(resList.get(i));
            tmp = tmp.right;
        }

        return res;
    }
}
